package codeRandomThoughts.Test377组合总和IV;

public class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;

        for (int j = 0; j <= target; j++) {
            for (int i = 0; i < nums.length; i++) {
                if (j >= nums[i]) {
                    //可以看做dp[7] = dp[6] + dp[4] + dp[3]
                    //最后一位可以是nums中的任何数字,所以我们遍历所有数字,然后把这些情况的排列数加起来
                    dp[j] += dp[j - nums[i]];
                }
            }
        }

        System.out.println("先遍历容量,再遍历物品");
        for (int i = 0; i <= target; i++) {
            System.out.print(dp[i]+" ");
        }
        return dp[target];
    }
}
